package tree;

public class FindBinaryTree {
    //构建二叉树内部类
    private static class TreeNode {
        int data;      //数据
        TreeNode lchild;  //左孩子
        TreeNode rchild;  //右孩子
    }

    //查找二叉树核心算法
    private static TreeNode Find(TreeNode root, int target) {
        if (root == null) {                 //如果根节点为空返回空
            return null;
        } else if (root.data == target) {         //如果root的数据等于target表示找到了
            return root;            //返回找到的根节点
        } else if (target < root.data) {             //如果目标值比根节点小 表示在左树里
            return Find(root.lchild, target);    //递归查找左孩子
        } else {             //否则的话说明target比根节点大 就去右子树里找
            return Find(root.rchild, target);//递归查找所有右孩子
        }
    }

    //创建查找二叉树
    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.data = 62;

        TreeNode binaryTree2 = new TreeNode();
        root.lchild = binaryTree2;
        binaryTree2.data = 58;

        TreeNode binaryTree3 = new TreeNode();
        binaryTree2.lchild = binaryTree3;
        binaryTree3.data = 47;

        TreeNode binaryTree4 = new TreeNode();
        binaryTree3.lchild = binaryTree4;
        binaryTree4.data = 35;

        TreeNode binaryTree5 = new TreeNode();
        binaryTree4.rchild = binaryTree5;
        binaryTree5.data = 37;

        TreeNode binaryTree6 = new TreeNode();
        binaryTree3.rchild = binaryTree6;
        binaryTree6.data = 51;

        TreeNode binaryTree7 = new TreeNode();
        root.rchild = binaryTree7;
        binaryTree7.data = 88;

        TreeNode binaryTree8 = new TreeNode();
        binaryTree7.lchild = binaryTree8;
        binaryTree8.data = 73;

        TreeNode binaryTree9 = new TreeNode();
        binaryTree7.rchild = binaryTree9;
        binaryTree9.data = 99;

        TreeNode binaryTree10 = new TreeNode();
        binaryTree9.lchild = binaryTree10;
        binaryTree10.data = 93;

        TreeNode treeNode = Find(root, 93);
        System.out.println(treeNode == null ? "没有这个数" : treeNode.data);
    }
}
